package 优先算法.滑动窗口.找到字符串中所有字母异位词;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution so = new Solution();
        String s = "abab";
        String p = "ab";
        List<Integer> list = so.findAnagrams(s, p);
        System.out.println(list);
    }
}
//count更新
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> answer = new ArrayList<Integer>();
        int[] hash1 = new int[26];
        for(int i = 0; i < p.length(); i++){
            hash1[p.charAt(i)-97]++;
        }
        int[] hash2 = new int[26];
        int n = s.length();
        int m = p.length();
        int right = 0,left = 0,count = 0;
        while(right < n){
            hash2[s.charAt(right) - 97]++;
            if(hash2[s.charAt(right) - 97] <= hash1[s.charAt(right++) - 97]){
                count++;
            }

            if((right - left) > m){
                if(hash2[s.charAt(left) - 97] <= hash1[s.charAt(left) - 97]){
                    count--;
                }
                hash2[s.charAt(left++)- 97]--;

            }
            if((right - left) == m && count == m){
                answer.add(left);
            }
        }
        return answer;
    }
}
class Solution1 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> answer = new ArrayList<Integer>();
        int[] hash1 = new int[26];
        for(int i = 0; i < p.length(); i++){
            hash1[p.charAt(i)-97]++;
        }
        int[] hash2 = new int[26];
        int n = s.length();
        int right = 0,left = 0;
        while(right < n){
            hash2[s.charAt(right++)- 97]++;
            if((right - left) > p.length()){
                hash2[s.charAt(left++)- 97]--;
            }
            if((right - left) == p.length()){
                if(check(hash2,hash1)){
                    answer.add(left);
                }
            }
        }
        return answer;
    }
    public static boolean check(int[]hash2,int[]hash1){
        for(int i = 0; i < hash1.length;i++){
            if(hash1[i] != hash2[i]){
                return false;
            }
        }
        return true;
    }
}